package main

//#link: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
import (
	"strconv"
	"strings"
	. "whoops/leetcode/common"
)

func main() {

}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	result := []string{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node != nil {
			result = append(result, strconv.Itoa(node.Val))
			queue = append(queue, node.Left)
			queue = append(queue, node.Right)

		} else {
			result = append(result, "X")
		}
	}
	return strings.Join(result, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "X" {
		return nil
	}
	list := strings.Split(data, ",")
	val, _ := strconv.Atoi(list[0])
	root := &TreeNode{Val: val}
	queue := []*TreeNode{root}
	cursor := 1
	for cursor < len(list) {
		node := queue[0]
		queue = queue[1:]

		leftValStr := list[cursor]
		rightValStr := list[cursor+1]
		if leftValStr != "X" {
			leftVal, _ := strconv.Atoi(leftValStr)
			leftNode := &TreeNode{Val: leftVal}
			node.Left = leftNode
			queue = append(queue, leftNode)
		}
		if rightValStr != "X" {
			rightVal, _ := strconv.Atoi(rightValStr)
			rightNode := &TreeNode{Val: rightVal}
			node.Right = rightNode
			queue = append(queue, rightNode)
		}
		cursor = cursor + 2
	}
	return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */
